package com.lazily.set_;


import java.util.HashSet;

/**
 * @Author:  GZQ
 * @date:  2025/5/6 22:08
 * @description: HashSet 底层源码分析
 * @version: 1.0
 */

@SuppressWarnings({"all"})
public class HashSetSource {
	// 程序入口
	public static void main(String[] args) {

		HashSet hashSet = new HashSet();
		hashSet.add("java");// 到此位置, 第一次add分析完毕
		hashSet.add("python");// 到此位置, 第一次add分析完毕
		hashSet.add("java");
		System.out.println("hashSet: " + hashSet);

		/*
		源码解读: HashSet
		1. 执行 HashSet()
			public HashSet() {
				map = new HashMap<>();
			}
		2. 执行 add()
			public boolean add(E e) { // e = "java"
				return map.put(e, PRESENT)==null; // PRESENT = private static final Object PRESENT = new Object();
			}
		3. 执行 put(), 该方法会执行 hash(key) 得到对应的hash值 算法h = key.hashCode() ^ (h >>> 16);
			 public V put(K key, V value) {// key = "java" value = PRESENT 共享
				return putVal(hash(key), key, value, false, true);
			}
		4. 执行 putVal
			final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
						   boolean evict) {
				Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义了辅助变量
				// table 就是 HashMap 的一个数组, 类型是 Node[]
				// if 语句表示如果当前table 是null, 或者 大小 = 0
				// 就是第一次扩容, 到16个空间
				if ((tab = table) == null || (n = tab.length) == 0)
					n = (tab = resize()).length;
				// (1) 根据key, 得到hash 去计算该 key 应该存放到 table 表的那个索引位置
				// 并且把这个位置的对象, 赋给 p
				// (2) 判断p 是否为null
				// (2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java(要存入的字符串)", value=PRESENT)
				// (2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null);
				if ((p = tab[i = (n - 1) & hash]) == null)
					tab[i] = newNode(hash, key, value, null);
				else {
					// 开发技巧: 在需要局部变量(辅助变量)时候, 在创建
					Node<K,V> e; K k;  //
					// 如果当前索引位置对应链表的第一个元素和准备添加的key的hash值一样
					// 并且满足下面两个条件之一:
					// (1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
					// (2) p 指向的Node 结点的 key 的equals() 方法 和准备加入的key比较后相同
					if (p.hash == hash &&
						((k = p.key) == key || (key != null && key.equals(k))))
						e = p;
					// 在判断 p 是不是一颗红黑树,
					// 如果是一颗红黑树, 就调用 putTreeVal, 来进行添加
					else if (p instanceof TreeNode)
						e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
					else { // 如果table 对应的索引位置, 已经是一个链表, 就使用for循环比较
						   // (1) 依次和该链表的每一个元素比较后, 都不相同, 则加入到该链表的最后
						   // 	  注意在把元素添加到链表后, 立即判断 该链表是否已经达到8个节点,
						   // 	  就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
						   // 		注意: 在转成红黑树时, 要进行判断, 判断条件
						   // 		 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
						   //             resize();
						   // 		如果上面条件成立, 先table扩容,
						   //  		只有上面的条件成立时, 才进行转成红黑树
						   // (2) 依次和该链表的每一个元素比较过程中, 如果有相同情况, 就直接break
						for (int binCount = 0; ; ++binCount) {
							if ((e = p.next) == null) {
								p.next = newNode(hash, key, value, null);
								if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
									treeifyBin(tab, hash);
								break;
							}
							if (e.hash == hash &&
								((k = e.key) == key || (key != null && key.equals(k))))
								break;
							p = e;
						}
					}
					if (e != null) { // existing mapping for key
						V oldValue = e.value;
						if (!onlyIfAbsent || oldValue == null)
							e.value = value;
						afterNodeAccess(e);
						return oldValue;
					}
				}
				++modCount;
				//size 就是我们每加入一个结点 Node(k,v,h,next), size++
				if (++size > threshold)
					resize(); // 扩容
				afterNodeInsertion(evict);
				return null;
			}
		 */
	}
}
